闲话
这场一个小时四十分钟做完D的就有200名了.不过感觉我VP的时候还是差了一点,CD都差那么一点,key idea也想了个大半.
A. Prime Subtraction
题目大意:给定两个整数和.保证比大.问两者的差是否可以表示成一个质数的若干倍的形式.
思路
一开始看错题了以为是幂,结果只是和.简单讨论一下就行了:
①如果差为偶数显然就满足了
②如果差为奇数且为,无解.
③如果差为奇数且不是,必然有解:因为他要么是一个质数,要么是一个合数,一个质数一定是乘自身,一个合数一定是若干个质因数相乘,因此一定有解.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int T;scanf("%d",&T);
while(T--)
{
ll y,x;scanf("%lld%lld",&x,&y);
ll sub = x - y;
if(sub % 2 == 0) puts("YES");
else if(sub == 1) puts("NO");
else puts("YES");
}
return 0;
}
B. Kill 'Em All
题目大意:坐标轴分成两边,以为界限.的部分是陷阱,的部分是怪物的据点.给出个怪物的坐标.你手上有一把武器,他每次可以指定一个位置发射一个炮弹造成一次爆炸,若炮弹的落点坐标是对于在位置上的怪物而言,在爆炸后有三种情况:
①,则死亡.
②,往左边移动单位.
③,往右边移动单位.
注意一次爆炸是没有覆盖范围的,所有敌人都会被影响.
如果一个怪物坐标达到或以下,则会被陷阱杀死.怪物不会自行移动,问你最少要发射几枚炮弹才能消灭所有的敌人,只需输出数量,不需要输出具体方案.
数据范围:
思路
显然要考虑的之后最右边的敌人是否被杀死了.对于每次发射而言,如果把一个怪物推向右边则毫无意义,如果放在最后一个怪物右边,不如放在最后一个怪物身上,因为这一定会炸死最后一个怪物,如果不放的话不一定会杀死最后一个怪物.
因此整个算法流程就非常明显了,就是每次选最后一个怪物,直接炸死他,让前一个成为新的坐标最靠右的,看他是不是已经死了就可以了.不过影响是累加的,所以除了让坐标减少之外,还要额外记录之前炸了多远.简单维护一下就可以.
另外由于坐标可能有重复,所以先去个重,避免讨论重复的问题.以及这个范围还是很大的,注意防范爆int.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 1e5+7;
signed main()
{
int T;scanf("%lld",&T);
while(T--)
{
int n,r;scanf("%lld%lld",&n,&r);
vector<int> pos;
for(int i = 1,x;i <= n;++i) scanf("%lld",&x),pos.push_back(x);
sort(pos.begin(),pos.end());
pos.erase(unique(pos.begin(),pos.end()),pos.end());
int res = 0,tot = 0;
while(pos.size() && pos.back() > 0)
{
pos.pop_back();
if(!pos.empty()) pos.back() -= r + tot;
tot += r;
++res;
}
printf("%lld\n",res);
}
return 0;
}
C. Standard Free2play
原题大意:你开始在高的悬崖上,悬崖侧边每一个单位剧里都有一个台阶,开始只有个被打开.数据默认高的台阶是打开的,只有被打开的台阶才可以站上去.如果站在高的台阶上(这个时候必须是打开的),你不能直接跳下去,只能变换的状态为关闭并落下,关闭的同时,的状态也会变化一次.你不能跌落超过两个单位高的高度,即从跌落到是可以的,但是到是不行的.游戏到的时候结束,为了保证你能到,允许你在游戏过程中开挂,任意改变一个位置的板子的状态.问你最少要开几次挂才能完成游戏,只需输出结果而不需要输出方案.
数据范围:
初始打开的个板子以坐标的形式给出.
思路
观察复杂度可以看出来,这个题要么是二分答案去写一个,要么是一个单纯的贪心,因为复杂度不可能直接跟有关,最多也就是.经过分析之后发现不那么好写,考虑后者.
如果现在是位置,如果下一个板子的高度不比现在的高度高,就跳过.直到有一个平台的高度是比他低的位置,显然高度这次之后会直接到,就是这块板子的下一个位置,接下来需要一定的分情况讨论了:首先我是从的前面一个位置下来的,我是把之前的一个板子状态反转导致翻转了才下来的,这个时候,如果是连续的,也就是的话,我可以直接下来到上,否则就必须开挂,并且高度不能落在上而是上.之后注意前后的关系模拟就可以了.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+7;
int a[N],f[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int h,n;scanf("%d%d",&h,&n);
for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
int res = 0;
for(int i = 2;i <= n;++i)
{
if(h <= a[i]) continue;
h = a[i] + 1;
if(i < n)
{
if(a[i + 1] == a[i] - 1) h = a[i + 1];
else ++res,h = a[i];
}
else if(h > 2) ++res;
}
printf("%d\n",res);
}
return 0;
}
D. AB-string
题目大意:一个字符串定义是牛逼的,当且仅当他所有的字符都属于一个连续的回文子串,并且这个回文子串的长度要.给定一个字符串,计算他有多少个子串是牛逼的.输出结果即可.
数据范围:
字符串中只包含有A或B
思路
对于一整个串来说,他一共有个子串,从里面挖掉不合法的串就是答案了.考虑什么样的串才是不合法的:显然当一个A和一个B单独的在一起的时候是不合法的,进而形如ABBBB的也肯定不合法.于是可以推出这个题的结论:当子串形如ABBBB,AAAAB,BBBBA,AAAAB的时候这样的串是不合法的.从每一个位置出发往两边找就可以了,每有一个就记录一个.
不过这个题还没完,这样打上去会发现样例的答案偏小,如果偏小意味着不牛逼的子串的数量多了,模拟一下样例之后可以发现是因为AB或BA这样的形式会被算进不牛逼的子串额外一次,最后多做一次遍历就可以解决这个问题了.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+7;
char s[N];
int main()
{
int n;scanf("%d",&n);
ll res = 1ll*n * (n - 1) / 2,bad = 0;
scanf("%s",s + 1);
for(int i = 1;i <= n;++i)
{
if(s[i] == 'A')
{
for(int j = i - 1;j >= 1;--j)
{
if(s[j] == 'B') ++bad;
else break;
}
for(int j = i + 1;j <= n;++j)
{
if(s[j] == 'B') ++bad;
else break;
}
}
else if(s[i] == 'B')
{
for(int j = i - 1;j >= 1;--j)
{
if(s[j] == 'A') ++bad;
else break;
}
for(int j = i + 1;j <= n;++j)
{
if(s[j] == 'A') ++bad;
else break;
}
}
}
for(int i = 1;i <= n - 1;++i)
if(s[i] != s[i + 1])
--bad;
printf("%lld\n",res - bad);
return 0;
}